{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# If you need to import additional packages or classes, please import here.\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Rule:\n",
    "    def __init__(self, ip_or_cidr, action, goto_chain=None):\n",
    "        self.network, self.mask = self.parse_network(ip_or_cidr)\n",
    "        self.action = action\n",
    "        self.goto_chain = goto_chain\n",
    "        \n",
    "    def parse_network(self, ip_or_cidr):\n",
    "        if '/' in ip_or_cidr:\n",
    "            ip, prefix_len = ip_or_cidr.split('/')\n",
    "            prefix_len = int(prefix_len)\n",
    "        else:\n",
    "            ip = ip_or_cidr\n",
    "            prefix_len = 32\n",
    "        ip_parts = list(map(int, ip.split('.')))\n",
    "        mask = (0xFFFFFFFF << (32 - prefix_len)) & 0xFFFFFFFF\n",
    "        ip_value = (ip_parts[0] << 24) | (ip_parts[1] << 16) |(ip_parts[2] << 8) | ip_parts[3]\n",
    "        return ip_value, mask\n",
    "    \n",
    "    def matches(self, ip):\n",
    "        ip_parts = list(map(int,ip.split('.')))\n",
    "        ip_value = (ip_parts[0] << 24) | (ip_parts[1] << 16) |(ip_parts[2] << 8) | ip_parts[3]\n",
    "        return (ip_value & self.mask) == (self.network & self.mask)\n",
    "    \n",
    "def proc_rule(n, cmds):\n",
    "    chains = defaultdict(deque)\n",
    "    res = []\n",
    "    \n",
    "    for cmd in cmds:\n",
    "        parts = cmd.split()\n",
    "        op = parts[0]\n",
    "        if op == 'I':\n",
    "            chain_name, ip_or_cidr, action = parts[1], parts[2], parts[3]\n",
    "            chains[chain_name].appendleft(Rule(ip_or_cidr, action))\n",
    "        elif op=='A':\n",
    "            chain_name, ip_or_cidr, action = parts[1], parts[2], parts[3]\n",
    "            if action=='G':\n",
    "                goto_chain = parts[4]\n",
    "                chains[chain_name].appendleft(Rule(ip_or_cidr, action, goto_chain))\n",
    "            else:\n",
    "                chains[chain_name].appendleft(Rule(ip_or_cidr, action))\n",
    "        elif op=='D':\n",
    "            chain_name, ip_or_cidr, action = parts[1], parts[2], parts[3]\n",
    "            for rule in chains[chain_name]:\n",
    "                if rule.network == Rule(ip_or_cidr, action).network and rule.mask == Rule(ip_or_cidr, action).mask and rule.action == Rule(ip_or_cidr, action).action:\n",
    "                    chains[chain_name].remove(rule)\n",
    "                    break\n",
    "        elif op=='M':\n",
    "            ip=parts[1]\n",
    "            result = match_ip(chains, ip)\n",
    "            res.append(result)\n",
    "    return res\n",
    "\n",
    "def match_ip(chains, ip):\n",
    "    chain_queue = deque(['c0'])\n",
    "    while chain_queue:\n",
    "        cur_chain=chain_queue.popleft()\n",
    "        for rule in chains[cur_chain]:\n",
    "            if rule.matches(ip):\n",
    "                if rule.action=='G':\n",
    "                    chain_queue.append(rule.goto_chain)\n",
    "                    break\n",
    "                else:\n",
    "                    return rule.action\n",
    "                \n",
    "    return 'U'     \n",
    "        \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    n = int(input())\n",
    "    cmds = [input().strip() for _ in range(n)]\n",
    "\n",
    "    res = proc_rule(n, cmds)\n",
    "    print(''.join(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# If you need to import additional packages or classes, please import here.\n",
    "\n",
    "def func(func, stack, path, visited, func_recall, func_stack, K, res):\n",
    "    if stack > K:\n",
    "        res.append((True, path.copy(), stack))\n",
    "        return True\n",
    "    \n",
    "    visited.add(func)\n",
    "    is_of = False\n",
    "    \n",
    "    for next_func in func_recall.get(func, []):\n",
    "        if next_func not in visited:\n",
    "            path.append(next_func)\n",
    "            stack += func_stack[next_func]\n",
    "            if func(next_func, stack, path, visited, func_recall, func_stack, K, res):\n",
    "                is_of = True\n",
    "                break\n",
    "            path.pop()\n",
    "            stack -= func_stack[next_func]\n",
    "    visited.remove(func)  \n",
    "    if not is_of:\n",
    "        res.append((False, path.copy(), stack))\n",
    "    return is_of\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # N\n",
    "    N = int(input())\n",
    "    func_stack = {}\n",
    "    for i in range(N):\n",
    "        line = input().split(' ')\n",
    "        func_stack[line[0]] = int(line[1])\n",
    "    # M\n",
    "    M = int(input())\n",
    "    func_recall = {}\n",
    "    for i in range(M):\n",
    "        recall = input().split(' ')\n",
    "        func_recall[recall[0]] = recall[1:]\n",
    "        if i==0:\n",
    "            start_func = recall[0]\n",
    "    # K\n",
    "    K = int(input())\n",
    "    \n",
    "    res = []    \n",
    "    func(start_func, func_stack[start_func], [start_func], set(), func_recall, func_stack, K, res)\n",
    "\n",
    "    max_stack,max_path = 0,None\n",
    "    for is_of, path, stack in res:\n",
    "        if stack > max_stack:\n",
    "            max_path = path\n",
    "        if is_of:\n",
    "            print('true '+'-'.join(path)+' '+str(stack))\n",
    "            # return \n",
    "    print('flase '+''-''.join(max_path)+' '+str(max_stack))\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
